package leetcode_121_140;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class wordBreak_139 {
    /**
     *给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。
     *
     * 注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        /**
         * 初步思路是利用字典中符合条件的单词自由组合所有可能性
         * 超时了
         * 想到了可以加入记忆化，即某个位置之前已经计算过，往后怎样都无法进行拼接，就记录下来
         * 2ms
         */
        int len=s.length();
        HashMap<Integer,List<StringBuilder>>map=new HashMap<>();  //k为单词长度，value为该长度的所有单词
        for (String word : wordDict) {
            int wordLen=word.length();
            if ( wordLen<= len) {  //长度不大于s的长度
                //添加到相同长度单词的集合中
                if(map.containsKey(wordLen)){
                    map.get(wordLen).add(new StringBuilder(word));
                }else {
                    List<StringBuilder>words=new ArrayList<>();
                    words.add(new StringBuilder(word));
                    map.put(wordLen,words);
                }
            }
        }
        boolean[] momo=new boolean[s.length()];         //是否无法继续拼接
        if(function(map,s.length(),new StringBuilder(),s,momo))
                return true;
        return false;
    }

    /**
     * @param map 不同长的单词的集合
     * @param len 实时单词距离目标单词的长度差
     * @param Sb 实时单词
     * @param s
     * @param momo 记忆数组
     */
    boolean function(HashMap<Integer,List<StringBuilder>>map,int len,StringBuilder Sb,String s,boolean[] momo){
        if(len==0)
            return true;
        if(momo[Sb.length()]==true) //此处之后无法组合单词拼接成功
           return false;

        for(int i=len;i>0;i--){  //优先拼接长单词
            if(map.containsKey(i)){
                for(StringBuilder sb:map.get(i)){
                    boolean flag=true; //该单词是否可以拼接
                    for (int t = 0; t < sb.length(); t++) {     //判断该单词是否可以拼接到对应位置
                        if (sb.charAt(t) != s.charAt(s.length() - len + t)) {
                            flag=false;
                            break;
                        }
                    }
                    if(flag){
                        if (function(map, len - sb.length(), new StringBuilder(Sb).append(sb), s, momo))
                            return true;
                        else
                            momo[Sb.length()+sb.length()]=true; //此时的Sb+sb组成的语句后面没有办法组成完成语句
                    }
                }
            }
        }
        return false;
    }


    /**
     * 简洁的动态规划
     * @param s
     * @param wordDict
     * @return
     */
    public boolean wordBreak2(String s, List<String> wordDict) {
        //动态规划
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (String word : wordDict) {
                if (i < word.length()) continue;
                if (s.substring(0, i).endsWith(word)) {
                    if (dp[s.substring(0, i - word.length()).length()]) {
                        dp[i] = true;
                    }
                }
            }
        }
        return dp[s.length()];
    }
}
